package code;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Code93 {
    public List<String> restoreIpAddresses(String s) {
        List<String> result=new ArrayList<String>();
        Set<String> set=new HashSet<String>();
        
        int i,j,k;
        for(i=0;i<3;i++){
        	int t=i;
        	String s1=s.substring(0,i+1);
        	if(Integer.parseInt(s1)>255)
        		continue;
        	for(j=i+1;j<t+4 && j<s.length();j++){
        		int o=j;
        		String s2=s.substring(i+1, j+1);
        		if(Integer.parseInt(s2)>255)
        			continue;
        		for(k=j+1;k<o+4 && k<s.length();k++){
        			String s3=s.substring(j+1,k+1);
        			if(Integer.parseInt(s3)>255)
        				continue;
        			String s4=s.substring(k+1,s.length());
        			if(s4.length()==0 || s4.length()>3 || Integer.parseInt(s4)>255)
        				continue;
        			int a=Integer.parseInt(s1);
        			int b=Integer.parseInt(s2);
        			int c=Integer.parseInt(s3);
        			int d=Integer.parseInt(s4);
        			//有前导0也不行
        			if(hasPreZero(s1) || hasPreZero(s2) || hasPreZero(s3) || hasPreZero(s4))
        				continue;
        			String ans=a+"."+b+"."+c+"."+d;
        			if(set.contains(ans))
        				continue;
        			set.add(ans);
        			result.add(ans);
        		}
        	}
        }
        return result;
    }
    boolean hasPreZero(String s){
    	if(s.length()<=1)	return false;
    	if(s.charAt(0)=='0')	return true;
    	return false;
    }
    public static void main(String[] args){
    	Code93 code=new Code93();
    	code.restoreIpAddresses("010010");
    }
}
